Full text search (FTS) systems search for relevant documents based on key words entered by a system user. The user enters a set of terms, referred to as tokens, and the FTS system retrieves documents containing all of the terms in the set. For example, Lucene (described at http://lucene.apache.org/) and SQLite's FTS module (described at http://www.sqlite.org/cvstrac/wiki?p=FtsUsage) are both FTS systems.
Often a user wants to combine FTS with a spatial search. For instance, a web-based mapping application may allow a user to zoom into a certain region of a map and then enter one or more search terms, such as “restaurant” or “hotel.” The web-based mapping application may then overlay push-pin icons over the map identifying where restaurants or hotels are located in the displayed region.
Generally, there are three approaches to execute a location based full text search. First, a spatial search may be conducted to return all points of interest within a geographic area. A full text search may then be conducted on the set of returned points of interest using one or more entered search tokens. This approach may be efficient if the spatial search is somewhat selective (i.e., a relatively small geographic area). Second, a full text search may be conducted first followed by a spatial search conducted upon the returned list of full text search results. This approach may be efficient if the full text search is somewhat selective. Third, a full text search and a spatial search may be conducted in parallel and the intersection of the two result sets may constitute the result set. This approach may be efficient if both searches are rather selective.
However, when the spatial search and the full text search are both rather unselective, none of these three approaches are particularly efficient. One example in which the spatial search and the full text search are both rather unselective is if a user conducted a search for “Pizza” within Chicago, Ill. Thus, it would be beneficial to have a location based full text search system that works efficiently when the single search criteria are unselective but the combination of them is selective.